import covertool
#import random, math

covertool.cover("avl.py:3") #avl.py:3
outputdebug = False 

def debug(msg):
    covertool.cover("avl.py:6") #avl.py:6
    if outputdebug:
        covertool.cover("avl.py:7") #avl.py:7
        print msg

class Node:
    def __init__(self, key):
        covertool.cover("avl.py:11") #avl.py:11
        self.key = key
        covertool.cover("avl.py:12") #avl.py:12
        self.left = None 
        covertool.cover("avl.py:13") #avl.py:13
        self.right = None 




class AVLTree:
    def __init__(self, *args):
        covertool.cover("avl.py:20") #avl.py:20
        self.node = None 
        covertool.cover("avl.py:21") #avl.py:21
        self.height = -1  
        covertool.cover("avl.py:22") #avl.py:22
        self.balance = 0; 
        
        covertool.cover("avl.py:24") #avl.py:24
        if len(args) == 1: 
            covertool.cover("avl.py:25") #avl.py:25
            for i in args[0]: 
                covertool.cover("avl.py:26") #avl.py:26
                self.insert(i)
                
    def height(self):
        covertool.cover("avl.py:29") #avl.py:29
        if self.node: 
            covertool.cover("avl.py:30") #avl.py:30
            return self.node.height 
        else: 
            covertool.cover("avl.py:32") #avl.py:32
            return 0 
    
    def is_leaf(self):
        covertool.cover("avl.py:35") #avl.py:35
        return (self.height == 0) 
    
    def insert(self, key):
        covertool.cover("avl.py:38") #avl.py:38
        tree = self.node
        
        covertool.cover("avl.py:40") #avl.py:40
        newnode = Node(key)
        
        covertool.cover("avl.py:42") #avl.py:42
        if tree == None:
            covertool.cover("avl.py:43") #avl.py:43
            self.node = newnode 
            covertool.cover("avl.py:44") #avl.py:44
            self.node.left = AVLTree() 
            covertool.cover("avl.py:45") #avl.py:45
            self.node.right = AVLTree()
            covertool.cover("avl.py:46") #avl.py:46
            debug("Inserted key [" + str(key) + "]")
        
        elif key < tree.key: 
            covertool.cover("avl.py:49") #avl.py:49
            self.node.left.insert(key)
            
        elif key > tree.key: 
            covertool.cover("avl.py:52") #avl.py:52
            self.node.right.insert(key)
        
        else: 
            covertool.cover("avl.py:55") #avl.py:55
            debug("Key [" + str(key) + "] already in tree.")
            
        covertool.cover("avl.py:57") #avl.py:57
        self.rebalance() 
        
    def rebalance(self):
        covertool.cover("avl.py:60") #avl.py:60
        ''' 
        covertool.cover("avl.py:61") #avl.py:61
        Rebalance a particular (sub)tree
        covertool.cover("avl.py:62") #avl.py:62
        ''' 
        # key inserted. Let's check if we're balanced
        covertool.cover("avl.py:64") #avl.py:64
        self.update_heights(False)
        covertool.cover("avl.py:65") #avl.py:65
        self.update_balances(False)
        covertool.cover("avl.py:66") #avl.py:66
        while self.balance < -1 or self.balance > 1: 
            covertool.cover("avl.py:67") #avl.py:67
            if self.balance > 1:
                covertool.cover("avl.py:68") #avl.py:68
                if self.node.left.balance < 0:  
                    covertool.cover("avl.py:69") #avl.py:69
                    self.node.left.lrotate() # we're in case II
                    covertool.cover("avl.py:70") #avl.py:70
                    self.update_heights()
                    covertool.cover("avl.py:71") #avl.py:71
                    self.update_balances()
                covertool.cover("avl.py:72") #avl.py:72
                self.rrotate()
                covertool.cover("avl.py:73") #avl.py:73
                self.update_heights()
                covertool.cover("avl.py:74") #avl.py:74
                self.update_balances()
                
            covertool.cover("avl.py:76") #avl.py:76
            if self.balance < -1:
                covertool.cover("avl.py:77") #avl.py:77
                if self.node.right.balance > 0:  
                    covertool.cover("avl.py:78") #avl.py:78
                    self.node.right.rrotate() # we're in case III
                    covertool.cover("avl.py:79") #avl.py:79
                    self.update_heights()
                    covertool.cover("avl.py:80") #avl.py:80
                    self.update_balances()
                covertool.cover("avl.py:81") #avl.py:81
                self.lrotate()
                covertool.cover("avl.py:82") #avl.py:82
                self.update_heights()
                covertool.cover("avl.py:83") #avl.py:83
                self.update_balances()


            
    def rrotate(self):
        # Rotate left pivoting on self
        covertool.cover("avl.py:89") #avl.py:89
        debug ('Rotating ' + str(self.node.key) + ' right') 
        covertool.cover("avl.py:90") #avl.py:90
        A = self.node 
        covertool.cover("avl.py:91") #avl.py:91
        B = self.node.left.node 
        covertool.cover("avl.py:92") #avl.py:92
        T = B.right.node 
        
        covertool.cover("avl.py:94") #avl.py:94
        self.node = B 
        covertool.cover("avl.py:95") #avl.py:95
        B.right.node = A 
        covertool.cover("avl.py:96") #avl.py:96
        A.left.node = T 

    
    def lrotate(self):
        # Rotate left pivoting on self
        covertool.cover("avl.py:101") #avl.py:101
        debug ('Rotating ' + str(self.node.key) + ' left') 
        covertool.cover("avl.py:102") #avl.py:102
        A = self.node 
        covertool.cover("avl.py:103") #avl.py:103
        B = self.node.right.node 
        covertool.cover("avl.py:104") #avl.py:104
        T = B.left.node 
        
        covertool.cover("avl.py:106") #avl.py:106
        self.node = B 
        covertool.cover("avl.py:107") #avl.py:107
        B.left.node = A 
        covertool.cover("avl.py:108") #avl.py:108
        A.right.node = T 
        
            
    def update_heights(self, recurse=True):
        covertool.cover("avl.py:112") #avl.py:112
        if not self.node == None: 
            covertool.cover("avl.py:113") #avl.py:113
            if recurse: 
                covertool.cover("avl.py:114") #avl.py:114
                if self.node.left != None: 
                    covertool.cover("avl.py:115") #avl.py:115
                    self.node.left.update_heights()
                covertool.cover("avl.py:116") #avl.py:116
                if self.node.right != None:
                    covertool.cover("avl.py:117") #avl.py:117
                    self.node.right.update_heights()
            
            covertool.cover("avl.py:119") #avl.py:119
            self.height = max(self.node.left.height,self.node.right.height) + 1 
        else: 
            covertool.cover("avl.py:121") #avl.py:121
            self.height = -1 
            
    def update_balances(self, recurse=True):
        covertool.cover("avl.py:124") #avl.py:124
        if not self.node == None: 
            covertool.cover("avl.py:125") #avl.py:125
            if recurse: 
                covertool.cover("avl.py:126") #avl.py:126
                if self.node.left != None: 
                    covertool.cover("avl.py:127") #avl.py:127
                    self.node.left.update_balances()
                covertool.cover("avl.py:128") #avl.py:128
                if self.node.right != None:
                    covertool.cover("avl.py:129") #avl.py:129
                    self.node.right.update_balances()

            covertool.cover("avl.py:131") #avl.py:131
            self.balance = self.node.left.height - self.node.right.height 
        else: 
            covertool.cover("avl.py:133") #avl.py:133
            self.balance = 0 

    def delete(self, key):
        # debug("Trying to delete at node: " + str(self.node.key))
        covertool.cover("avl.py:137") #avl.py:137
        if self.node != None: 
            covertool.cover("avl.py:138") #avl.py:138
            if self.node.key == key: 
                covertool.cover("avl.py:139") #avl.py:139
                debug("Deleting ... " + str(key))  
                covertool.cover("avl.py:140") #avl.py:140
                if self.node.left.node == None and self.node.right.node == None:
                    covertool.cover("avl.py:141") #avl.py:141
                    self.node = None # leaves can be killed at will 
                # if only one subtree, take that 
                elif self.node.left.node == None: 
                    covertool.cover("avl.py:144") #avl.py:144
                    self.node = self.node.right.node
                elif self.node.right.node == None: 
                    covertool.cover("avl.py:146") #avl.py:146
                    self.node = self.node.left.node
                
                # worst-case: both children present. Find logical successor
                else:  
                    covertool.cover("avl.py:150") #avl.py:150
                    replacement = self.logical_successor(self.node)
                    covertool.cover("avl.py:151") #avl.py:151
                    if replacement != None: # sanity check 
                        covertool.cover("avl.py:152") #avl.py:152
                        debug("Found replacement for " + str(key) + " -> " + str(replacement.key))  
                        covertool.cover("avl.py:153") #avl.py:153
                        self.node.key = replacement.key 
                        
                        # replaced. Now delete the key from right child 
                        covertool.cover("avl.py:156") #avl.py:156
                        self.node.right.delete(replacement.key)
                    
                covertool.cover("avl.py:158") #avl.py:158
                self.rebalance()
                covertool.cover("avl.py:159") #avl.py:159
                return  
            elif key < self.node.key: 
                covertool.cover("avl.py:161") #avl.py:161
                self.node.left.delete(key)  
            elif key > self.node.key: 
                covertool.cover("avl.py:163") #avl.py:163
                self.node.right.delete(key)
                        
            covertool.cover("avl.py:165") #avl.py:165
            self.rebalance()
        else: 
            covertool.cover("avl.py:167") #avl.py:167
            return 

    def logical_predecessor(self, node):
        covertool.cover("avl.py:170") #avl.py:170
        ''' 
        covertool.cover("avl.py:171") #avl.py:171
        Find the biggest valued node in LEFT child
        covertool.cover("avl.py:172") #avl.py:172
        ''' 
        covertool.cover("avl.py:173") #avl.py:173
        node = node.left.node 
        covertool.cover("avl.py:174") #avl.py:174
        if node != None: 
            covertool.cover("avl.py:175") #avl.py:175
            while node.right != None:
                covertool.cover("avl.py:176") #avl.py:176
                if node.right.node == None: 
                    covertool.cover("avl.py:177") #avl.py:177
                    return node 
                else: 
                    covertool.cover("avl.py:179") #avl.py:179
                    node = node.right.node  
        covertool.cover("avl.py:180") #avl.py:180
        return node 
    
    def logical_successor(self, node):
        covertool.cover("avl.py:183") #avl.py:183
        ''' 
        covertool.cover("avl.py:184") #avl.py:184
        Find the smallese valued node in RIGHT child
        covertool.cover("avl.py:185") #avl.py:185
        ''' 
        covertool.cover("avl.py:186") #avl.py:186
        node = node.right.node  
        covertool.cover("avl.py:187") #avl.py:187
        if node != None: # just a sanity check  
            
            covertool.cover("avl.py:189") #avl.py:189
            while node.left != None:
                covertool.cover("avl.py:190") #avl.py:190
                debug("LS: traversing: " + str(node.key))
                covertool.cover("avl.py:191") #avl.py:191
                if node.left.node == None: 
                    covertool.cover("avl.py:192") #avl.py:192
                    return node 
                else: 
                    covertool.cover("avl.py:194") #avl.py:194
                    node = node.left.node  
        covertool.cover("avl.py:195") #avl.py:195
        return node 

    def check_balanced(self):
        covertool.cover("avl.py:198") #avl.py:198
        if self == None or self.node == None: 
            covertool.cover("avl.py:199") #avl.py:199
            return True
        
        # We always need to make sure we are balanced 
        covertool.cover("avl.py:202") #avl.py:202
        self.update_heights()
        covertool.cover("avl.py:203") #avl.py:203
        self.update_balances()
        covertool.cover("avl.py:204") #avl.py:204
        return ((abs(self.balance) < 2) and self.node.left.check_balanced() and self.node.right.check_balanced())  
        
    def inorder_traverse(self):
        covertool.cover("avl.py:207") #avl.py:207
        if self.node == None:
            covertool.cover("avl.py:208") #avl.py:208
            return [] 
        
        covertool.cover("avl.py:210") #avl.py:210
        inlist = [] 
        covertool.cover("avl.py:211") #avl.py:211
        l = self.node.left.inorder_traverse()
        covertool.cover("avl.py:212") #avl.py:212
        for i in l: 
            covertool.cover("avl.py:213") #avl.py:213
            inlist.append(i) 

        covertool.cover("avl.py:215") #avl.py:215
        inlist.append(self.node.key)

        covertool.cover("avl.py:217") #avl.py:217
        l = self.node.right.inorder_traverse()
        covertool.cover("avl.py:218") #avl.py:218
        for i in l: 
            covertool.cover("avl.py:219") #avl.py:219
            inlist.append(i) 
    
        covertool.cover("avl.py:221") #avl.py:221
        return inlist 

    def display(self, level=0, pref=''):
        covertool.cover("avl.py:224") #avl.py:224
        '''
        covertool.cover("avl.py:225") #avl.py:225
        Display the whole tree. Uses recursive def.
        covertool.cover("avl.py:226") #avl.py:226
        TODO: create a better display using breadth-first search
        covertool.cover("avl.py:227") #avl.py:227
        '''        
        covertool.cover("avl.py:228") #avl.py:228
        self.update_heights()  # Must update heights before balances 
        covertool.cover("avl.py:229") #avl.py:229
        self.update_balances()
        covertool.cover("avl.py:230") #avl.py:230
        if(self.node != None): 
            covertool.cover("avl.py:231") #avl.py:231
            print '-' * level * 2, pref, self.node.key, "[" + str(self.height) + ":" + str(self.balance) + "]",
            covertool.cover("avl.py:232") #avl.py:232
            if self.is_leaf():
                covertool.cover("avl.py:233") #avl.py:233
                print 'L'
            else:
                covertool.cover("avl.py:235") #avl.py:235
                print
            covertool.cover("avl.py:236") #avl.py:236
            if self.node.left != None: 
                covertool.cover("avl.py:237") #avl.py:237
                self.node.left.display(level + 1, '<')
            covertool.cover("avl.py:238") #avl.py:238
            if self.node.left != None:
                covertool.cover("avl.py:239") #avl.py:239
                self.node.right.display(level + 1, '>')

    
